BZOJ4695 最假女选手 < SegBeats >

Problem

最假女选手

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中，如愿以偿的得到了最假女选手的奖项。但是作为主办人的为了证明确实在放水，决定出一道基础题考察的姿势水平。给定一个长度为序列，编号从到。要求支持下面几种操作：

给一个区间加上一个数
把一个区间里小于的数变成
把一个区间里大于的数变成
求区间的和
求区间的最大值
求区间的最小值

Input

第一行一个整数表示序列长度
第二行个整数表示初始序列
第三行一个整数表示操作个数
接下来行，每行三或四个整数，第一个整数表示操作类型，接下来或表述操作数

Output

对于每个类型的操作，输出一行一个整数表示答案

Sample Input

Sample Output

HINT

时,
或时，

标签：SegBeats 线段树

Solution

参见吉老师的冬令营课件。

像课件里那样维护最大值、最大值个数、严格次大值、最小值、最小值个数、严格次小值、区间加标记、区间和，丧心病狂分类更新即可。注意只有区间和需要开，这样即省空间又省常数。

好久没写过上行的代码了…
强烈建议先对拍再交，否则容易卡住评测…

Code

#include <bits/stdc++.h>
#define ls (v<<1)
#define rs (v<<1|1)
#define mid ((s+t)>>1)
#define MAX_N 500000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct node {int mx1, mx2, mxc, mi1, mi2, mic, tag;	lnt s;} tr[(MAX_N<<2)+5];
void update(int v) {
    tr[v].s = tr[ls].s+tr[rs].s;
    if (tr[ls].mx1 == tr[rs].mx1)
        tr[v].mx1 = tr[ls].mx1, 
        tr[v].mxc = tr[ls].mxc+tr[rs].mxc, 
        tr[v].mx2 = max(tr[ls].mx2, tr[rs].mx2);
    else if (tr[ls].mx1 > tr[rs].mx1)
        tr[v].mx1 = tr[ls].mx1, 
        tr[v].mxc = tr[ls].mxc, 
        tr[v].mx2 = max(tr[ls].mx2, tr[rs].mx1);
    else
        tr[v].mx1 = tr[rs].mx1, 
        tr[v].mxc = tr[rs].mxc, 
        tr[v].mx2 = max(tr[ls].mx1, tr[rs].mx2);
    if (tr[ls].mi1 == tr[rs].mi1)
        tr[v].mi1 = tr[ls].mi1, 
        tr[v].mic = tr[ls].mic+tr[rs].mic, 
        tr[v].mi2 = min(tr[ls].mi2, tr[rs].mi2);
    else if (tr[ls].mi1 < tr[rs].mi1)
        tr[v].mi1 = tr[ls].mi1, 
        tr[v].mic = tr[ls].mic, 
        tr[v].mi2 = min(tr[ls].mi2, tr[rs].mi1);
    else
        tr[v].mi1 = tr[rs].mi1, 
        tr[v].mic = tr[rs].mic, 
        tr[v].mi2 = min(tr[ls].mi1, tr[rs].mi2);
}
void updmx(int v, int s, int t, int x) {
    tr[v].s -= 1LL*tr[v].mxc*(tr[v].mx1-x);
    tr[v].mx1 = x, tr[v].mi1 = min(x, tr[v].mi1);
    if (tr[v].mx1^tr[v].mi1) tr[v].mi2 = min(x, tr[v].mi2);
    else
        tr[v].mx2 = -INF, tr[v].mi2 = INF, 
        tr[v].s = 1LL*(t-s+1)*x, tr[v].mxc = tr[v].mic = t-s+1;
}
void updmi(int v, int s, int t, int x) {
    tr[v].s += 1LL*tr[v].mic*(x-tr[v].mi1);
    tr[v].mi1 = x, tr[v].mx1 = max(x, tr[v].mx1);
    if (tr[v].mx1^tr[v].mi1) tr[v].mx2 = max(x, tr[v].mx2);
    else
        tr[v].mx2 = -INF, tr[v].mi2 = INF, 
        tr[v].s = 1LL*(t-s+1)*x, tr[v].mxc = tr[v].mic = t-s+1;
}
void downtag(int v, int s, int t) {
    int x = tr[v].tag;	tr[v].tag = 0;
    if (x)
        tr[ls].mx1 += x, tr[ls].mx2 += x, 
        tr[ls].mi1 += x, tr[ls].mi2 += x, 
        tr[ls].s += 1LL*(mid-s+1)*x, tr[ls].tag += x, 
        tr[rs].mx1 += x, tr[rs].mx2 += x, 
        tr[rs].mi1 += x, tr[rs].mi2 += x, 
        tr[rs].s += 1LL*(t-mid)*x, tr[rs].tag += x;
    if (tr[v].mx1 < tr[ls].mx1 && tr[v].mx1 > tr[ls].mx2) updmx(ls, s, mid, tr[v].mx1);
    if (tr[v].mi1 > tr[ls].mi1 && tr[v].mi1 < tr[ls].mi2) updmi(ls, s, mid, tr[v].mi1);
    if (tr[v].mx1 < tr[rs].mx1 && tr[v].mx1 > tr[rs].mx2) updmx(rs, mid+1, t, tr[v].mx1);
    if (tr[v].mi1 > tr[rs].mi1 && tr[v].mi1 < tr[rs].mi2) updmi(rs, mid+1, t, tr[v].mi1);
}
void build(int v, int s, int t) {
    if (s == t) {
        int x;	read(x);
        tr[v].mx1 = tr[v].mi1 = x, tr[v].mxc = tr[v].mic = 1;
        tr[v].mx2 = -INF, tr[v].mi2 = INF, tr[v].s = x;	return;
    }
    build(ls, s, mid), build(rs, mid+1, t), update(v);
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        tr[v].mx1 += x, tr[v].mx2 += x;
        tr[v].mi1 += x, tr[v].mi2 += x;
        tr[v].s += 1LL*(t-s+1)*x;
        tr[v].tag += x;	return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(ls, s, mid, l, r, x);
    if (r >= mid+1) modify(rs, mid+1, t, l, r, x);
    update(v);
}
void optmx(int v, int s, int t, int l, int r, int x) {
    if (tr[v].mi1 >= x) return;
    if (s >= l && t <= r && x < tr[v].mi2)
        {updmi(v, s, t, x);	return;}
    downtag(v, s, t);
    if (l <= mid) optmx(ls, s, mid, l, r, x);
    if (r >= mid+1) optmx(rs, mid+1, t, l, r, x);
    update(v);
}
void optmi(int v, int s, int t, int l, int r, int x) {
    if (tr[v].mx1 <= x) return;
    if (s >= l && t <= r && x > tr[v].mx2)
        {updmx(v, s, t, x);	return;}
    downtag(v, s, t);
    if (l <= mid) optmi(ls, s, mid, l, r, x);
    if (r >= mid+1) optmi(rs, mid+1, t, l, r, x);
    update(v);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].s;
    downtag(v, s, t);	lnt ret = 0LL;
    if (l <= mid) ret += query(ls, s, mid, l, r);
    if (r >= mid+1) ret += query(rs, mid+1, t, l, r);
    update(v);	return ret;
}
int getmx(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].mx1;
    downtag(v, s, t);	int ret = -INF;
    if (l <= mid) ret = max(ret, getmx(ls, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, getmx(rs, mid+1, t, l, r));
    update(v);	return ret;
}
int getmi(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].mi1;
    downtag(v, s, t);	int ret = INF;
    if (l <= mid) ret = min(ret, getmi(ls, s, mid, l, r));
    if (r >= mid+1) ret = min(ret, getmi(rs, mid+1, t, l, r));
    update(v);	return ret;
}
int main() {
    int n, T;	read(n), build(1, 1, n), read(T);
    while (T--) {
        int opt, l, r, x;	read(opt);
        if (opt == 1) read(l), read(r), read(x), modify(1, 1, n, l, r, x);
        if (opt == 2) read(l), read(r), read(x), optmx(1, 1, n, l, r, x);
        if (opt == 3) read(l), read(r), read(x), optmi(1, 1, n, l, r, x);
        if (opt == 4) read(l), read(r), printf("%lld\n", query(1, 1, n, l, r));
        if (opt == 5) read(l), read(r), printf("%d\n", getmx(1, 1, n, l, r));
        if (opt == 6) read(l), read(r), printf("%d\n", getmi(1, 1, n, l, r));
    }
    return 0;
}